package BackTrackingPackage;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Lzm
 * @version 1.0
 */
/*重点是得出树形结构*/
  /*树层上不能重复*/
public class permuteUnique_ {
  LinkedList<Integer> list = new LinkedList<>();
  List<List<Integer>> result = new ArrayList<>();
  boolean[] used;
  @Test
  public void permuteUniqueTest(){
    int[] nums = new int[]{1,1,2};
    used = new boolean[nums.length];
    Arrays.fill(used,false);
    Arrays.sort(nums);
    backTracking(nums);
    System.out.println(result);
  }

  public void backTracking(int[] nums){
    if (list.size() == nums.length){
      result.add(new LinkedList<>(list));
      return;
    }
    /*树层去重
    * 因为前一个nums所形成的树枝能够覆盖这个nums形成的数值*/
    for(int i = 0 ; i < nums.length ; i ++){
      if (i > 0 && nums[i] == nums[i- 1] && !used[i - 1]){
        continue;
      }
      else{
        /*树枝去重, 取过的元素就不能取了
        * 例如, list=[1] 从[1,1,2]中取
        * 那就不能在从[1,1,2]中取第一个1了*/
        if (used[i] == false){
          used[i] = true;
          list.add(nums[i]);
          backTracking(nums);
          used[i] = false;
          list.removeLast();
        }

      }
    }
  }
}
